from typing import List


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


def mergeKLists(lists: List[ListNode]) -> ListNode:
    n = len(lists)

    if n == 0: return None
    if n == 1: return lists[0]
    if n == 2: return merge2Lists(lists[0], lists[1])

    mid = n // 2

    return merge2Lists(mergeKLists(lists[:mid]), mergeKLists(lists[mid:]))


def merge2Lists(l1: ListNode, l2: ListNode) -> ListNode:
    res = ListNode(0)
    combined = res
    while l1 or l2:
        if l1 and l2:
            if l1.val < l2.val:
                combined.next = ListNode(l1.val)
                l1 = l1.next
            else:
                combined.next = ListNode(l2.val)
                l2 = l2.next
            combined = combined.next
        elif l1:
            combined.next = l1
            break
        else:
            combined.next = l2
            break
    return res.next
